{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Palindrome IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makePalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效的回文 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、仅由小写英文字母组成的字符串 <code>s</code> 。在一步操作中，你可以将 <code>s</code> 中的任一字符更改为其他任何字符。</p>\n",
    "\n",
    "<p>如果你能在 <strong>恰</strong> 执行一到两步操作后使 <code>s</code> 变成一个回文，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"abcdba\"\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 能让 s 变成回文，且只用了一步操作的方案如下:\n",
    "- 将 s[2] 变成 'd' ，得到 s = \"abddba\" 。\n",
    "执行一步操作让 s 变成一个回文，所以返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"aa\"\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 能让 s 变成回文，且只用了两步操作的方案如下:\n",
    "- 将 s[0] 变成 'b' ，得到 s = \"ba\" 。\n",
    "- 将 s[1] 变成 'b' ，得到s = \"bb\" 。\n",
    "执行两步操作让 s 变成一个回文，所以返回 true 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"abcdef\"\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释:</strong> 不存在能在两步操作以内将 s 变成回文的办法，所以返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-palindrome-iv](https://leetcode.cn/problems/valid-palindrome-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-palindrome-iv](https://leetcode.cn/problems/valid-palindrome-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcdba\"', '\"aa\"', '\"abcdef\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        i, j = 0, len(s)-1\n",
    "\n",
    "        cnt = 0\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "            j -= 1\n",
    "\n",
    "        return cnt <= 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        i, j = 0, len(s)-1\n",
    "\n",
    "        cnt = 0\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "            j -= 1\n",
    "            \n",
    "            if cnt > 2:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        c=0\n",
    "        for i in range(n//2):\n",
    "            if s[i]!=s[-1-i]:\n",
    "                c+=1\n",
    "                if c>2:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        return sum(x!=y for x,y in zip(s,s[::-1]))//2<=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        ss=s[:n-(n//2):-1]\n",
    "        return sum(x!=y for x,y in zip(s,s[::-1]))//2<=2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        i, j = 0, len(s)-1\n",
    "\n",
    "        cnt = 0\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "            j -= 1\n",
    "            \n",
    "            # 不相同的最多2对，即最多换2次；可以0对，按题意可以换相同的回文对，凑够1次或2次\n",
    "            if cnt > 2:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        return sum(s[i] != s[~i] for i in range(len(s) >> 1)) <= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        ans = 0\n",
    "        l, r = 0, len(s)-1\n",
    "        while l < r:\n",
    "            if s[l] != s[r]:\n",
    "                ans += 1\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return ans <= 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        count = 0\n",
    "        n = len(s)\n",
    "        for i in range(n // 2):\n",
    "            if s[i] != s[n - i - 1]:\n",
    "                count += 1\n",
    "        if count <= 2:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        need = 0\n",
    "        l,r = 0,len(s) - 1\n",
    "        while l < r:\n",
    "            if s[l] != s[r]:\n",
    "                need += 1\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return True if need <= 2 else False\n",
    "\n",
    "# 作者：Chap\n",
    "# 链接：https://leetcode.cn/problems/valid-palindrome-iv/solutions/1656606/python3-shuang-zhi-zhen-by-chap_-rno0/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        need = 0\n",
    "        l,r = 0,len(s) - 1\n",
    "        while l < r:\n",
    "            if s[l] != s[r]:\n",
    "                need += 1\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return True if need <= 2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        i=0\n",
    "        j=len(s)-1\n",
    "        cnt=0\n",
    "\n",
    "        while i<j:\n",
    "            \n",
    "            if s[i]==s[j]:\n",
    "                i+=1\n",
    "                j-=1\n",
    "            else:\n",
    "                cnt+=1\n",
    "                i+=1\n",
    "                j-=1\n",
    "            if cnt>2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        count = 0\n",
    "        l = 0 \n",
    "        r = len(s) - 1\n",
    "        while l <= r:\n",
    "            if s[l] != s[r]:\n",
    "                count += 1\n",
    "            if count > 2:\n",
    "                return False\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makePalindrome(self, s: str) -> bool:\n",
    "        t = s[::-1]\n",
    "        cnt = 0\n",
    "        for i in range(len(s)//2):\n",
    "            if s[i] != t[i]:\n",
    "                cnt += 1\n",
    "                if cnt > 2:\n",
    "                    return False\n",
    "        return True\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
